package Lagou.Queue;
//例 2：循环队列
//【题目】设计一个可以容纳 k 个元素的循环队列。


class Queue02 {
    //方案一 使用used
     class MyCircularQueue1 {
         private int used = 0;
         private int front = 0;
         private int rear = 0;
         private int capacity = 0;

         //循环队列的存储空间
         private int[] a = null;
         public MyCircularQueue1(int k) {
             //初始化队列
             capacity = k;
             a = new int[capacity];
         }

         //将value放到队列中,成功返回true
         public boolean enQueue(int value) {
                //如果放满了
             if (isFull()) {
                 return false;
             }
             //如果没有放满，那么就用a[rear]来存放新进来的元素
             a[rear] = value;
             //rear注意取模
             rear = (rear + 1) % capacity;
             used++;
             return true;
         }

         //删除队首元素，成功返回true
         public boolean deQueue() {
             //判空
             if (isEmpty()) return false;
             //第一个元素取出
             int ret = a[front];
             //注意取模
             front = (front + 1) % capacity;
             used--;
             return true;
         }

         //得到队首元素，如果为空，返回-1
         public int Front() {
             //判空
             if (isEmpty()) return -1;
             return a[front];
         }

         //得到队尾元素，如果队列为空，返回-1
         public int Rear(){
             //判空
             if (isEmpty()) return -1;
             int tail = (rear - 1 + capacity) % capacity;
             return a[tail];
         }

         //看一下循环队列是否为空
         public boolean isEmpty(){
             return used == 0;
         }

         //看一下循环队列是否已放满k个元素
         public boolean isFull(){
             return used == capacity;
         }
     }

     //方案二 使用k+1空间
     class MyCircularQueue2 {
         // 队列的头部元素所在位置
         private int front = 0;
         // 队列的尾巴
         // 注意我们采用的是前开后闭原则
         // [front, rear)
         private int rear = 0;
         private int[] a = null;
         private int capacity = 0;

         public MyCircularQueue2(int k) {
             // 初始化队列，注意此时队列中元素个数为
             // k + 1
             capacity = k + 1;
             a = new int[k + 1];
         }

         public boolean enQueue(int value) {
             // 如果已经满了，无法入队
             if (isFull()) {
                 return false;
             }
             // 把元素放到rear位置
             a[rear] = value;
             // rear向后移动
             rear = (rear + 1) % capacity;
             return true;
         }

         public boolean deQueue() {
             // 如果为空，无法出队
             if (isEmpty()) {
                 return false;
             }
             // 出队之后，front要向前移
             front = (front + 1) % capacity;
             return true;
         }

         public int Front() {
             // 如果能取出第一个元素，取a[front];
             return isEmpty() ? -1 : a[front];
         }

         public int Rear() {
             // 由于我们使用的是前开后闭原则
             // [front, rear)
             // 所以在取最后一个元素时，应该是
             // (rear - 1 + capacity) % capacity;
             int tail = (rear - 1 + capacity) % capacity;
             return isEmpty() ? -1 : a[tail];
         }

         public boolean isEmpty() {
             // 队列是否为空
             return front == rear;
         }

         public boolean isFull() {
             // rear与front之间至少有一个空格
             // 当rear指向这个最后的一个空格时，
             // 队列就已经放满了!
             return (rear + 1) % capacity == front;
         }
     }
}
